package org.example.myleet.p494;

import java.util.*;

public class Solution {
    private static final int AMPLIFICATION = 1000;

    public int findTargetSumWays(int[] nums, int target) {
        //放大以防止超出
        int[] dp = new int[2 * AMPLIFICATION + 2];
        dp[nums[0] + AMPLIFICATION] = 1;
        dp[-nums[0] + AMPLIFICATION] = 1;
        //待观察的数字
        Queue<Integer> queue = new LinkedList<>();
        queue.add(nums[0] + AMPLIFICATION);
        queue.add(-nums[0] + AMPLIFICATION);
        for (int i = 1; i < nums.length; ++i) {
            Set<Integer> destinations = new HashSet<>();
            Set<Integer> lastNumberSet = new HashSet<>();
            //待计算的目标及得到的结果
            Map<Integer, Integer> destinationCountMap = new HashMap<>();
            int count;
            while (!queue.isEmpty()) {
                Integer lastNum = queue.poll();
                //+
                int destination = lastNum + nums[i];
                destinations.add(destination);
                count = destinationCountMap.getOrDefault(destination, 0);
                count += dp[lastNum];
                destinationCountMap.put(destination, count);
                //-
                destination = lastNum - nums[i];
                destinations.add(destination);
                count = destinationCountMap.getOrDefault(destination, 0);
                count += dp[lastNum];
                destinationCountMap.put(destination, count);
                lastNumberSet.add(lastNum);
            }
            //清除本次计算中没有出现的结果
            for (Integer lastNum : lastNumberSet) {
                if (!destinations.contains(lastNum)) {
                    dp[lastNum] = 0;
                }
            }
            //本次计算结果填入对应的可能数字中
            for (Map.Entry<Integer, Integer> entry : destinationCountMap.entrySet()) {
                dp[entry.getKey()] = entry.getValue();
            }
            //可能的数字加入到下一回合待使用
            for (Integer destination : destinations) {
                queue.offer(destination);
            }
        }
        return dp[target + AMPLIFICATION];
    }
}
